class Solution:
    def findMinHeightTrees(self, n: int, edges: list):
        mid_list = [[0, [], i][:] for i in range(n)]
        for lists in edges:
            mid_list[lists[0]][0] += 1
            mid_list[lists[0]][1].append(lists[1])
            mid_list[lists[1]][0] += 1
            mid_list[lists[1]][1].append(lists[0])
        count = 0
        while True:
            mid_res = []
            for i in range(n):
                if mid_list[i][0] == 1:
                    count += 1
                    mid_res.append(i)
                    mid_list[i][0] = -1
                elif mid_list[i][0] == 0:
                    return [i]
            if count == n:
                return mid_res
            for num in mid_res:
                for i in mid_list[num][1]:
                    mid_list[i][0] -= 1


class Solution:
    def findMinHeightTrees(self, n: int, edges: list):
        mid_list = {i: [0, []][:] for i in range(n)}
        for lists in edges:
            mid_list[lists[0]][0] += 1
            mid_list[lists[0]][1].append(lists[1])
            mid_list[lists[1]][0] += 1
            mid_list[lists[1]][1].append(lists[0])
        count = 0
        while True:
            mid_res = []
            for index, lists in mid_list.items():
                if lists[0] == 1:
                    count += 1
                    mid_res.append(index)
                elif lists[0] == 0:
                    return [index]
            if count == n:
                return mid_res
            for index in mid_res:
                for num in mid_list[index][1]:
                    mid_list[num][0] -= 1
                    mid_list[num][1].remove(index)
                mid_list.pop(index)


class Solution:
    def findMinHeightTrees(self, n: int, edges: list):
        if not edges:
            return [0]
        mid_list = {i: [][:] for i in range(n)}
        for lists in edges:
            mid_list[lists[0]].append(lists[1])
            mid_list[lists[1]].append(lists[0])
        count = 0
        mid_set = {0, 1}
        while True:
            mid_res = []
            for index, lists in mid_list.items():
                if len(lists) in mid_set:
                    mid_res.append(index)
            count += len(mid_res)
            if count == n:
                return mid_res
            for index in mid_res:
                for num in mid_list[index]:
                    mid_list[num].remove(index)
                mid_list.pop(index)


class Solution:
    def findMinHeightTrees(self, n: int, edges: list):
        if not edges:
            return [0]
        from collections import defaultdict
        mid_dict = defaultdict(list)
        for lists in edges:
            mid_dict[lists[0]].append(lists[1])
            mid_dict[lists[1]].append(lists[0])
        mid_res = {i for i in mid_dict if len(mid_dict[i]) == 1}
        count = len(mid_res)
        while count < n:
            mid_set = set()
            for index in mid_res:
                num = mid_dict[index].pop()
                mid_dict[num].remove(index)
                if len(mid_dict[num]) <= 1:
                    mid_set.add(num)
            mid_res = mid_set
            count += len(mid_res)
        return list(mid_res)


a = Solution()
print(a.findMinHeightTrees(n=4, edges=[[1, 0], [1, 2], [1, 3]]))
print(a.findMinHeightTrees(n=6, edges=[[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]))
